package 中等.搜索.深度优先搜索;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。
 * 你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/lexicographical-numbers/
 */
public class 字典序排数_386 {

    public static void main(String[] args) {

        System.out.println(new 字典序排数_386().lexicalOrder(105));

    }

    /**
     * 注意题目是排序[1,n]中所有数
     * 模拟排序
     * 1xx > 2xx
     * 如果1*10<=n，那么10将是第二小的，如果1*10*10<=n，那么100将是第三小的
     * 直至找到1*10*10*10>n，那么回退到上一层，如果1*10*10+x<=n x=[1,9]，添加
     *
     * @param n
     * @return
     */
    public List<Integer> lexicalOrder(int n) {
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= 9; i++) {
            sort(i, list, n);
        }
        return list;
    }

    public void sort(int num, List<Integer> list, int max) {
        if (num > max) {
            return;
        }
        list.add(num);
        for (int curNum = num * 10; curNum <= num * 10 + 9; curNum++) {
            if (curNum <= max) {  // 当前数字符合条件才递归，以减少栈的深度
                sort(curNum, list, max);
            }
        }
    }

}
